UVa/10127 - Ones/p10127.dpr

   1 program p10127;\r
   2 \r
   3 {$APPTYPE CONSOLE}\r
   4 \r
   5 function procesar(n : integer) : integer;\r
   6 {Explicación del algoritmo:\r
   7 \r
   8 Para hallar la longitud del múltiplo más pequeño que sea una cadena de 1111's\r
   9 lo que hago es hallar primero el múltiplo que me da en la posición de las\r
  10 unidades un 1 (Nótese que por ser un múltiplo no divisible por 2 ó 5 al construir\r
  11 su tabla del 0 al 9 habrá un múltiplo que termina en 0, otro en 1, otro 2, ... y\r
  12 otro en 9). Una vez hallado el mútiplo que me da un 1 en las unidades, lo\r
  13 multiplico por N y lo que "lleva" lo acumulo en la variable carry e incremento\r
  14 la cuenta correspondiente al resultado. Ahora repito lo mismo, sólo que no tengo\r
  15 que encontrar el múltiplo que sus unidades sean 1 sino el múltiplo que al sumarle\r
  16 carry sus unidades sean 1. Esto se hace hasta que carry sea 0.\r
  17 \r
  18 }\r
  19 var\r
  20   tabla : Array[0..9] of integer;\r
  21   carry, multiplo, i, ultimaCifra : integer;\r
  22 begin\r
  23   result := 0;\r
  24   for i := 0 to 9 do\r
  25     tabla[i] := n * i;\r
  26 \r
  27   ultimaCifra := 1;\r
  28   carry := 0;\r
  29 \r
  30   repeat\r
  31     //2\r
  32     multiplo := 0;\r
  33     while tabla[multiplo] mod 10 <> ultimaCifra do\r
  34       multiplo := multiplo + 1;\r
  35     //3 y 5\r
  36     carry := (n * multiplo + carry) div 10;\r
  37     //6\r
  38     i := carry;\r
  39     while (i mod 10 <> 1) do\r
  40       i := i + 1;\r
  41     ultimaCifra := i - carry;\r
  42     //4\r
  43     result := result + 1;\r
  44   until carry = 0;\r
  45 \r
  46 end;\r
  47 \r
  48 var\r
  49   n : integer;\r
  50 begin\r
  51   while not EOF do\r
  52     begin\r
  53       readLn(n);\r
  54       writeLn(procesar(n));\r
  55     end;\r
  56 end.\r
  57